// 实现 get 方法
// var obj = {a: {b: {c: 2}}}; console.log(get(obj, 'a.b.c')); // 输出 2
/**
 *
 * @param {数据源} obj
 * @param {路径字符串} path
 * @returns  根据路径返回值
 */
const get = (obj, path) => {
	let result = obj
	let keys = path.split('.')
	for (let key of keys) {
		if (result) {
			result = result[key]
		} else {
			return undefined
		}
	}
	return result
}
const obj = { a: { b: { c: 2 } } }
console.log(get(obj, 'a.b.c')) // 输出 2

// 把数组平分，实现 fn
// fn([1, 2, 3, 4, 5], 2) //结果为[[1,2],[3,4],[5]]
/**
 *
 * @param {数据源} arr
 * @param {每组的长度} size
 * @returns  数组平分
 */
const fn = (arr, size) => {
	let result = []
	for (let i = 0; i < arr.length; i += size) {
		result.push(arr.slice(i, i + size))
	}
	return result
}
console.log('fn', fn([1, 2, 3, 4, 5], 2))

/**
滑动窗口： 定长的滑动窗口/不定长的滑动窗口 =》 双指针
*/

// const maxAltitude = (heights, limit) => {

// }
// console.log(maxAltitude([14, 2, 27, -5, 28, 13, 39], 3));
/**
1. 排序
2.循环-2
定一个最小值
3. while left < right
4. 定义一个base 值
5.  左指针，右指针
6. 计算sum， 和 target 比较 diff
7. diff < min min = diff result = sum
8. sum > target 右指针左移
9. sum < target 左指针右移
10. 返回result
*/
const threeSumClosest = (arr, target) => {
	let n = arr.length
	if (n === 3) {
		return arr.reduce((prev, acc) => prev + acc)
	}
	arr.sort((a, b) => a + b)
	let min = Infinity
	let result
	for (let k = 0; k < n - 2; k++) {
		let baseNum = arr[k]
		let left = arr[k + 1]
		let right = arr[n - 1]
		while (left < right) {
			let sum = baseNum + left + right
			let diff = Math.abs(sum - target)
			if (diff < min) {
				min = diff
				result = sum
			}
			if (sum < target) {
				left++
			} else if (sum > target) {
				right--
			} else {
				return sum
			}
		}
	}
	return result
}
console.log(threeSumClosest([1, 2, 4, 8, 16, 32, 64, 128], 82))

console.log(threeSumClosest([-1, 2, 1, -4], 1)) // 输出: -3
console.log(threeSumClosest([1, 2, 3], 3)) // 输出: 6

// 3.6 验证回文串
// 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
// 说明：本题中，我们将空字符串定义为有效的回文串。
// 示例 1:
// 输入: "A man, a plan, a canal: Panama"
// 输出: true
// 示例 2:
// 输入: "race a car"
// 输出: false
const isPalindrome = (s) => {
	s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase()
	let l = 0
	let r = 0
	while (l < r) {
		if (s[l] !== s[r]) {
			return false
		}
		l++
		r--
	}
	return true
}
const findLongestWord = (s, dictionary) => {
	let res = ''
	for (let t of dictionary) {
		let i = 0
		let j = 0
		while (i < t.length && j < s.length) {
			if (t[i] === s[j]) {
				i++
			}
			j++
		}
		if (i === t.length) {
			if (t.length > res.length || (t.length == res.length && t < res)) {
				res = t
			}
		}
	}
	return res
}

console.log('www', findLongestWord('abpcplea', ['ale', 'apple', 'monkey', 'plea']))

const merge = (nums1, m, nums2, n) => {
	nums2 = nums2.slice(0, n)
	nums1.splice(m, nums1.length - m, ...nums2)
	nums1.sort((a, b) => a - b)
}
// var merge = function (nums1, m, nums2, n) {
// 	let p1 = 0,
// 		p2 = 0
// 	const sorted = new Array(m + n).fill(0)
// 	var cur
// 	while (p1 < m || p2 < n) {
// 		if (p1 === m) {
// 			cur = nums2[p2++]
// 		} else if (p2 === n) {
// 			cur = nums1[p1++]
// 		} else if (nums1[p1] < nums2[p2]) {
// 			cur = nums1[p1++]
// 		} else {
// 			cur = nums2[p2++]
// 		}
// 		sorted[p1 + p2 - 1] = cur
// 	}
// 	for (let i = 0; i != m + n; ++i) {
// 		nums1[i] = sorted[i]
// 	}
// 	console.log('nums1', nums1)
// }

merge([1, 2, 3, 0, 0, 0], 2, [2, 5, 6], 1)
// 3.3 搜索二维矩阵
// 编写一个高效的算法来搜索  m x n  矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
// 每行的元素从左到右升序排列。
// 每列的元素从上到下升序排列。
// 示例:
// 现有矩阵 matrix 如下：
// [
//   [1, 4, 7, 11, 15],
//   [2, 5, 8, 12, 19],
//   [3, 6, 9, 16, 22],
//   [10, 13, 14, 17, 24],
//   [18, 21, 23, 26, 30],
// ]
const searchMatrix = (matrix, target) => {
	let rows = matrix.length
	let cols = matrix[0].length
	let row = 0
	let col = cols - 1
	while (row < rows && col >= 0) {
		if (matrix[row][col] === target) {
			return true
		} else if (matrix[row][col] > target) {
			col--
		} else {
			row++
		}
	}
	return false
}
console.log(
	searchMatrix(
		[
			[1, 4, 7, 11, 15],
			[2, 5, 8, 12, 19],
			[3, 6, 9, 16, 22],
			[10, 13, 14, 17, 24],
			[18, 21, 23, 26, 30]
		],
		21
	)
)

// 3.5 分发饼干
// 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
// 注意：
// 你可以假设胃口值为正。
// 一个小朋友最多只能拥有一块饼干。
// 示例 1:

// 输入: [1,2,3], [1,1]

// 输出: 1

// 解释:
// 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
// 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
// 所以你应该输出1。
// 示例 2:

// 输入: [1,2], [1,2,3]

// 输出: 2

// 解释:
// 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
// 你拥有的饼干数量和尺寸都足以让所有孩子满足。
// 所以你应该输出2.
let findContentChildren = function (g, s) {
	g.sort((a, b) => a - b)
	s.sort((a, b) => a - b)
	let count = 0,
		child = 0,
		cookie = 0
	while (child < g.length && cookie < s.length) {
		if (g[child] == s[cookie]) {
			child++, count++
		}
		cookie++
	}
	return count
}
console.log(findContentChildren([1, 2, 3], [1, 1]))
console.log(findContentChildren([1, 2], [1, 2, 3]))
console.log(findContentChildren([7, 8, 9, 10], [5, 6, 7, 8]))

console.log(findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]))

var maxSlidingWindow = function (nums, k) {
	if (k === 0 || nums.length === 0) return []
	let l = 0
	let r = k - 1
	let max = []
	while (r < nums.length) {
		max.push(Math.max(...nums.slice(l, r + 1)))
		l++, r++
	}
	return max
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
